package B刷题.A栈和队列;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author wei.zhao
 * @description: 程序员代码面试指南：单调栈结构
 * @date 2022/12/6 15:00
 */
public class Code09_MonotonousStack {

    /**
     * 获取左、右两边比当前数小的最近位置，没有重复值
     */
    public static int[][] getNearLessNoRepeat(int[] arr) {
        int[][] result = new int[arr.length][];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                Integer pop = stack.pop();
                int[] popResult = new int[2];
                popResult[0] = stack.isEmpty() ? -1 : stack.peek();
                popResult[1] = i;
                result[pop] = popResult;
            }
            stack.add(i);
        }
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            int[] popResult = new int[2];
            popResult[0] = stack.isEmpty() ? -1 : stack.peek();
            popResult[1] = -1;
            result[pop] = popResult;
        }
        return result;
    }


    /**
     * 获取左、右两边比当前数小的最近位置
     */
    public static int[][] getNearLess(int[] arr) {
        int[][] result = new int[arr.length][];
        Stack<ArrayList<Integer>> stack = new Stack<>();
        // 遍历所有元素进栈
        for (int i = 0; i < arr.length; i++) {
            // 栈顶元素比当前元素大，一直弹出
            while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
                ArrayList<Integer> list = stack.pop();
                // 取位于下面位置的列表中最晚加入的那个
                int leftMin = stack.peek().isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
                int rightMin = i;
                for (Integer integer : list) {
                    result[integer][0]=leftMin;
                    result[integer][1]=rightMin;
                }
            }
            // 栈顶元素与当前相等
            if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
                stack.peek().add(i);
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                stack.add(list);
            }
        }
        // 剩余的元素全部出栈
        while (!stack.isEmpty()) {
            ArrayList<Integer> pop = stack.pop();
            int leftMin = stack.peek().isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
            int rightMin = -1;
            for (Integer integer : pop) {
                result[integer][0]=leftMin;
                result[integer][1]=rightMin;
            }
        }
        return result;
    }

}
